package code.c02_list.sqList;

/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/9/9 16:38
 * @package code.list
 * @description 顺序存储结构 —— 线性表
 */

public class SqListClass<E> {
    // 顺序表的初始容量
    final int initcapacity = 10;

    // 存放顺序表中的元素
    public E[] data;

    // 存放顺序表的长度
    public int size;

    //  存放顺序表的容量
    private int capacity;

    // 实现构造方法
    public SqListClass() {
        // 强制转换成E类型数组
        data = (E[]) new Object[initcapacity];
        capacity = initcapacity;
        size = 0;
    }

    /**
     * 扩大顺序表的容量操作
     *
     * @param newcapacity 新的容量数值
     */
    public void updatecapacity(int newcapacity) {
        E[] newdata = (E[]) new Object[newcapacity];
        for (int i = 0; i < size; i++) {
            newdata[i] = data[i];
        }
        capacity = newcapacity;
        data = newdata;
    }

    /**
     * 由 a 整体新建顺序表
     */
    public void createList(E[] a) {
        size = 0;
        for (int i = 0; i < a.length; i++) {
            // 如果元素已经满了，则进行扩容操作
            if (size == capacity) {
                updatecapacity(size * 2);
            }
            data[size] = a[i];
            size++; //添加元素的个数增加 1
        }
    }

    // ===========================实现基本方法==============================

    /**
     * 将元素e 添加到线性表的末尾
     *
     * @param e 元素 e
     */
    public void add(E e) {
        if (size == capacity) {
            updatecapacity(size * 2);
        }
        // 最后一个元素下标式 size -1 ,需要添加的元素的下标是 size
        data[size] = e;
        size++;
    }

    /**
     * 返回线性表的长度
     *
     * @return 线性表的长度
     */
    public int size() {
        return size;
    }

    /**
     * 设置线性表的长度
     * 该运算主要用于缩小线性表的长度，当参数newLen正确时（0 ≤ newLen ≤ size-1）
     * 设置长度size 为newLen,否则抛出异常
     *
     * @param newLen 顺序表新的长度
     */
    public void setsize(int newLen) {
        if (newLen < 0 || newLen > size) {
            throw new IllegalArgumentException("设置长度：newLen不在有效的范围内。");
        } else {
            size = newLen;
        }
    }

    /**
     * 求线性表中序号为 i 的元素
     *
     * @param i 序号 i
     * @return 元素E
     */
    public E getElem(int i) {
        // 检查下标是否越界
        if (i < 0 || i > size - 1) {// 最后一个元素的下标是 size - 1
            throw new IllegalArgumentException("查找：位置i不在有效的范围内。");
        }
        return (E) data[i];
    }

    /**
     * 设置线性表中序号为 i 的值
     *
     * @param i 序号 i
     * @param e 需要修改的元素
     */
    public void setElem(int i, E e) {
        if (i < 0 || i > size - 1) {
            throw new IllegalArgumentException("设置：位置i不在有效的范围内。");
        } else {
            data[i] = e;
        }
    }

    /**
     * 求线性表中第一个值为 e 的元素的需要
     *
     * @param e 元素 e
     * @return 序号
     */
    public int getNo(E e) {
        int i = 0;
        // 循环遍历元素的下标
        while (i < size && !data.equals(e)) {
            i++;
        }
        // 如果没有找到数组元素，则返回 -1
        if (i > size) {
            return -1;
        } else {
            return i;
        }
    }


    /**
     * 将i按行表中序号为 i 和 序号为 j 的元素交换位置
     *
     * @param i 序号i
     * @param j 序号j
     */
    public void swap(int i, int j) {
        if (i < 0 || i > size - 1) {
            throw new IllegalArgumentException("交换：位置i不在有效的范围内。");
        }

        if (j < 0 || j > size - 1) {
            throw new IllegalArgumentException("交换：位置j不在有效的范围内。");
        }

        E tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

    /**
     * 在线性表中插入e 作为第 i 个元素
     *
     * @param i 序号 i
     * @param e 元素 e
     */
    public void insert(int i, E e) {
        if (i < 0 || i > size) {
            throw new IllegalArgumentException("插入：位置i不在有效的范围内。");
        }
        // 判断是否需要扩容
        if (size == capacity) {
            updatecapacity(size * 2);
        }
        // 从后往前将元素向后移动一位
        for (int j = size; j > i; j--) {
            data[j] = data[i - 1];
        }
        // 插入元素
        data[i] = e;
        size++;
    }

    /**
     * 在线性表中删除第 i 个数据元素。
     *
     * @param i 被删除的元素的序号 i
     */
    public void delete(int i) {
        if (i < 0 || i > size - 1) {
            throw new IllegalArgumentException("删除：位置i不在有效的范围内。");
        }
        for (int j = i; j < size - 1; j++) {
            // 将data[i] 之后的所有的元素都向前移动一个位置
            data[j] = data[j + 1];
        }
        size--;

        // 缩容操作
        if (capacity > initcapacity && size == capacity / 4) {
            updatecapacity(capacity / 2);
        }
    }

    /**
     * 将线性表转换为字符串
     * @return 转换后的字符串
     */
    public String toString(){
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < size; i++) {
            ans.append(data[i].toString()).append(" ");
        }
        return ans.toString();
    }

}
